package n_04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author ChengMiao
 * @date 2021/6/28 16:17
 * @Desc No.4 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 */
public class Demo {
    public static void main(String[] args) {
        int [] nums1 = {1,3};
        int [] nums2 = {2,4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }


    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {

        // 12345
        // 12356
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;
        /**
         *  2
         *  ------- 0
         *  right= 1
         *  ------- 1
         *  right= 1
         *  ------- 2
         *  right= 2
         */
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
                right = nums1[aStart++];
            } else {
                right = nums2[bStart++];
            }
        }
        if ((len & 1) == 0)
            return (left + right) / 2.0;
        else
            return right;

    }

    public static  double findMedianSortedArrays(int[] nums1, int[] nums2) {

       List<Integer> list = new ArrayList<>();
        for (int i : nums1) {
            list.add(i);
        }

        for (int i : nums2) {
            list.add(i);
        }

        list.sort(Integer::compareTo);

        if(list.size()%2!=0){
            return list.get(list.size()/2 );
        }else{
            Integer i = list.get(list.size() / 2 - 1);
            Integer j = list.get(list.size() / 2);

            return (double) (i+j)/2;
        }
    }
}
